import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Solution542 {
    /**
     * 给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。
     * <p>
     * 两个相邻元素间的距离为 1 。
     * <p>
     * 示例 1:
     * 输入:
     * <p>
     * 0 0 0
     * 0 1 0
     * 0 0 0
     * 输出:
     * <p>
     * 0 0 0
     * 0 1 0
     * 0 0 0
     */
    public int[][] updateMatrix(int[][] matrix) {
        int[][] direction = {{-1,0},{1,0},{0,-1},{0,1}};
        int raws = matrix.length;
        int cols = matrix[0].length;
        int[][] res = new int[raws][cols];
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visit = new boolean[raws][cols];
        for (int i = 0; i < raws; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == 0) {
                    queue.add(new int[]{i, j});
                    visit[i][j] = true;
                }

            }
        }
        while (!queue.isEmpty()){
            int[] p = queue.poll();
            for (int i = 0; i < 4; i++) {
                int x = p[0] + direction[i][0];
                int y = p[1] + direction[i][1];
                if (x >=0 && y >=0 && x < raws && y < cols && !visit[x][y]){
                    res[x][y] = res[p[0]][p[1]] + 1;
                    queue.offer(new int[]{x,y});
                    visit[x][y] = true;
                }
            }
        }
        return res;
    }
}
